% !TEX root = sparsecut.tex
\subsection{Problem Statement and Our Results}\label{sec:results}

\subsubsection{Problem Statement}
In this paper, we consider the problem of finding a sparse cut in an undirected graph. Formally, given a graph $G = (V, E)$ with conductance $\phi$, we want to find a cut set whose conductance is close to $\phi$. Our goal is to design a distributed algorithm which finds a cut set with best possible approximation to the sparsity $\phi$.    

\subsubsection{Our Results}

%We present an approach to compute a sparse cut in distributed computing model. We use random walks to
%estimate the probability distribution which in turn can be used to find a
%sparse cut by adapting the method of Lov{\'a}sz and Simonovits \cite{LovaszS90,SpielmanT04,AndersenCL06}. 
Our main contribution is a distributed algorithm (in the CONGEST model) to find sparse cuts with approximation guarantees.
Our algorithm crucially uses random walks.
%The algorithms is presented in Algorithm~\ref{alg:sparsecut} and the main result is stated below. 

%\begin{lemma}[cf. Lemma \ref{lem:parallel-conductance}]
%Let $G = (V, E)$ be an undirected graph. Let $\pi = (1, 2, \ldots, n)$ be an ordering of $n$ vertices. Then one can compute the conductance of $n-1$ cuts $(\pi_j, \bar{\pi}_j), j = 1, 2, \ldots, n-1$ in $O(n)$ rounds where $\pi_j = \{1, 2, \ldots, j\}$.  
%\end{lemma} 

\begin{theorem}(cf. Section \ref{sec:sparse-cut})
\label{thm:algo1}
Given an $n$-node network $G$ with a cut of balance $b$ and conductance at most $\phi$, there is a distributed algorithm {\sc SparseCut} (cf. Algorithm \ref{alg:sparsecut}) that outputs a cut of conductance at most $\tilde O(\sqrt{\phi})$ with high probability, in $O(\frac{1}{b}(\frac{1}{\phi} + n)\log^2 n)$ rounds. In particular, to find a cut of constant balance, the {\sc SparseCut} algorithm takes $O((\frac{1}{\phi} + n)\log^2 n)$ rounds and finds a cut (if it exists) with similar approximation.  
\end{theorem}

Using the above result, we also show:

\begin{theorem}(cf. Section \ref{sec:local-cluster})
\label{thm:cluster}
Given an $n$-node network $G$ and  source node $s$, there is a  distributed algorithm that  outputs a {\em local} cluster in $O((\frac{1}{\phi} + n)\log^3 n)$ rounds, where $\phi$ is the conductance of the graph. 
\end{theorem}

To prove the running time bound, we derive a technical result on computing  conductances of $n$ (different) cuts in linear time (cf. Lemma \ref{lem:parallel-conductance}). We note that the time bound of  $\tilde O(\frac{1}{\phi} + n)$  is linear in $n$ (the number of nodes) and $1/\phi$.  From the definition of conductance (cf. Definition \ref{def:conductance}), it is clear that for every graph,
$1/\phi = O(m)$ ($m$ is the number of edges) and for many graphs it can be much smaller, e.g., for expanders it is $O(1)$. Hence, the running time of our algorithms can be significantly faster than the naive bound of $O(m)$ (cf. Section \ref{sec:distmodel}), especially in well-connected dense graphs. We next show a lower bound on the time needed for any distributed algorithm to compute a (non-trivial) sparse cut.

\begin{theorem}(cf. Section \ref{sec:lower-bound})
\label{thm:lb}
There is a $n$-node graph in which any distributed approximation algorithm  for computing sparsest cut (within any non-trivial approximation ratio)  will take $\tilde \Omega(\sqrt{n} + D)$ rounds, where $D$ is the diameter of the graph.
\end{theorem}

%Since $1/\phi = \Omega(D/\log n)$ (\cite{ChierichettiLP10}) for any graph, the above lower bound says that in general, one cannot hope to improve on the $1/\phi$ term
%of our upper bound. 










